COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00008 ENDMK
C⊗;
\input macro[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A78.Tex[254,mps]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, November 30, 1988}
\leftline{\sevenrm Unpublished draft}
\bigskip
\noindent{\bf Solutions to some takehome final problems}

\medskip
\line{{\bf (9).} The Undebugged Induction Principle\hfil}

\display 40pt:(1): Show $p(0)$.

\display 40pt:(2): Assume $p(x)$ is true for all $x≤n$. Show that $p(x)$ is
true for some $x>n$. Deduce $\forall x\, p(x)$.

Example: all natural numbers are of the form $2↑n-1$.

\display 40pt:(1): $0=2↑1-1$.

\display 40pt:(2): If $x=2↑n-1$, then $2x+1>x$, and $2x+1=2↑{n+1}-1$.

\noindent When this principle is debugged, it will be very useful on
problems like \# 9.

\medskip
\line{{\bf (10).}\hfil}

If a string is a computation of the PDM, it is pretty clear that it must be
a path through the graph. The operations must change the stack from~$\epsilon$
to~$\epsilon$; those other than push and pop are identity functions on the
stack, so omitting them makes no difference, and the push/pop operations,
by \# 9, belong to $L↓{G↓2}$.

If the string is a labeled path through the graph, etc., we need to
show that there is a sequence of instantaneous descriptions corresponding
to the computation steps.

Because the PDM is standardized, the sequence of input operations is

\medskip
\halign{\qquad\qquad #\hfil\cr
{\tt EOF} true {\tt READ} $a↓1$\cr
{\tt EOF} true {\tt READ} $a↓2$\cr
\quad $\vdots$\cr
{\tt EOF} true {\tt READ} $a↓n$\cr
{\tt EOF} false\cr}

\noindent
which can be executed on the input string $a↓1a↓2\ldots a↓n$. This requirement
is the reason for standardizing; otherwise we could have to worry about
non-executable sequences like

\medskip
\halign{\qquad\qquad #\hfil\cr
{\tt EOF} false {\tt EOF} true {\tt READ} $a$ {\tt EOF} false.\cr}

\noindent
One needs to show that if $xy$ is a string in $L↓{G↓2}$, the prefix~$x$
takes the empty stack into some possible value. Since $xy$ is a partial
function and $\epsilon$ is in the domain of~$xy$, it must be in the
domain of~$x$, and in fact $\epsilon\circ x$ is
unique. The rest is trivial.

\medskip
\line{{\bf (11).}\hfil}

Converting $L↓{(\,)[\,]}$ to $L↓{G↓2}$ is easily done by a GSM that does
character substitutions, by \# 7. Another GSM pads this language with
non-stack operations. A~third intersects it with the (regular) set of labeled
paths through the graph of the (standardized) PDM. Composing these three
GSMs gives one that maps $L↓{(\,)[\,]}$ into the computations of the PDM,
by \# 10.

\medskip
\line{{\bf (12).}\hfil}

Add one more GSM to the composition in \# 11, that substitutes $\epsilon$
for everything except characters of the PDM's output alphabet.

\noindent
{\bf Theorem.} In one direction trivial; in the other, mention that since
$L↓{(\,)[\,]}$ is a CFL, so are its GSM images.

\bye